package com.muchfish.algorithm.queue;


/**
 * <a href="https://leetcode.cn/problems/design-circular-deque/description/">题目：641. 设计循环双端队列</a>
 * <br>
 * 题目描述：<br>
 * 设计实现双端队列。
 * 实现 MyCircularDeque 类:
 * MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
 * boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
 * boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
 * boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
 * boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
 * int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
 * int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
 * boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
 * boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。
 * <br>
 * 解题思路： <br>
 *  方法一：数组<br>
 *
 *总结：
 * 双端循环队列和普通循环队列的主要区别在于对队列操作的灵活性和效率。
 *
 * 1. **普通循环队列**：
 *    - **定义**：普通循环队列是一个固定大小的数组，通过两个指针（`front` 和 `rear`）来表示队列的头部和尾部。
 *    - **插入操作**：只能在队尾插入元素。
 *    - **删除操作**：只能从队头删除元素。
 *    - **限制**：由于它只允许从队尾插入和从队头删除，因此操作较为单一。
 *
 * 2. **双端循环队列**（Deque，Double-ended Queue）：
 *    - **定义**：双端循环队列是一个可以从队头和队尾同时进行插入和删除操作的队列。
 *    - **插入操作**：可以在队头插入元素，也可以在队尾插入元素。
 *    - **删除操作**：可以从队头删除元素，也可以从队尾删除元素。
 *    - **灵活性**：它比普通循环队列更加灵活，允许在队列的两端同时进行操作。
 *
 * ### 总结：
 * - **普通循环队列**只能从队头删除，队尾插入，适用于先进先出（FIFO）结构。
 * - **双端循环队列**支持从两端进行插入和删除，适用于需要在两端进行操作的场景。
 */
public class Queue2 {
}
class MyCircularDeque {
    private int[] elements;
    private int rear, front;
    private int capacity;

    public MyCircularDeque(int k) {
        capacity = k + 1;
        rear = front = 0;
        elements = new int[k + 1];
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        elements[front] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}